{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #火星词典"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: alienOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #火星词典"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。</p>\n",
    "\n",
    "<p>给定一个字符串列表 <code>words</code> ，作为这门语言的词典，<code>words</code> 中的字符串已经 <strong>按这门新语言的字母顺序进行了排序</strong> 。</p>\n",
    "\n",
    "<p>请你根据该词典还原出此语言中已知的字母顺序，并 <strong>按字母递增顺序</strong> 排列。若不存在合法字母顺序，返回 <code>&quot;&quot;</code> 。若存在多种可能的合法字母顺序，返回其中 <strong>任意一种</strong> 顺序即可。</p>\n",
    "\n",
    "<p>字符串 <code>s</code> <strong>字典顺序小于</strong> 字符串 <code>t</code> 有两种情况：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在第一个不同字母处，如果 <code>s</code> 中的字母在这门外星语言的字母顺序中位于 <code>t</code> 中字母之前，那么&nbsp;<code>s</code> 的字典顺序小于 <code>t</code> 。</li>\n",
    "\t<li>如果前面 <code>min(s.length, t.length)</code> 字母都相同，那么 <code>s.length &lt; t.length</code> 时，<code>s</code> 的字典顺序也小于 <code>t</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [&quot;wrt&quot;,&quot;wrf&quot;,&quot;er&quot;,&quot;ett&quot;,&quot;rftt&quot;]\n",
    "<strong>输出：</strong>&quot;wertf&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [&quot;z&quot;,&quot;x&quot;]\n",
    "<strong>输出：</strong>&quot;zx&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [&quot;z&quot;,&quot;x&quot;,&quot;z&quot;]\n",
    "<strong>输出：</strong>&quot;&quot;\n",
    "<strong>解释：</strong>不存在合法字母顺序，因此返回 <code>&quot;&quot; 。</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 100</code></li>\n",
    "\t<li><code>words[i]</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 269&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/alien-dictionary/\">https://leetcode-cn.com/problems/alien-dictionary/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Jf1JuT](https://leetcode.cn/problems/Jf1JuT/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Jf1JuT](https://leetcode.cn/problems/Jf1JuT/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"wrt\",\"wrf\",\"er\",\"ett\",\"rftt\"]', '[\"z\",\"x\"]', '[\"z\",\"x\",\"z\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        chars = set()\n",
    "        for word in words:\n",
    "            for c in word:\n",
    "                chars.add(c)\n",
    "        before_count = {c: 0 for c in chars}\n",
    "        after = {c: [] for c in chars}\n",
    "        for i in range(len(words) - 1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i+1]\n",
    "            for k in range(min(len(word1), len(word2))):\n",
    "                c1, c2 = word1[k], word2[k]\n",
    "                if c1 != c2:\n",
    "                    before_count[c2] += 1\n",
    "                    after[c1].append(c2)\n",
    "                    break\n",
    "            else:\n",
    "                if len(word1) > len(word2):\n",
    "                    return ''\n",
    "        a = []\n",
    "        for c, v in before_count.items():\n",
    "            if v == 0:\n",
    "                a.append(c)\n",
    "        i = 0\n",
    "        while i < len(a):\n",
    "            c = a[i]\n",
    "            i += 1\n",
    "            for d in after[c]:\n",
    "                before_count[d] -= 1\n",
    "                if before_count[d] == 0:\n",
    "                    a.append(d)\n",
    "        return '' if len(a) < len(chars) else ''.join(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words):\n",
    "        # 构建图的邻接列表和入度列表\n",
    "        adj_list = {c: [] for word in words for c in word}\n",
    "        in_degree = {c: 0 for word in words for c in word}\n",
    "\n",
    "        # 根据相邻的单词构建图\n",
    "        for i in range(len(words) - 1):\n",
    "            curr_word = words[i]\n",
    "            next_word = words[i + 1]\n",
    "            min_len = min(len(curr_word), len(next_word))\n",
    "\n",
    "            # 找到两个单词第一个不同的字符\n",
    "            for j in range(min_len):\n",
    "                if curr_word[j] != next_word[j]:\n",
    "                    if next_word[j] not in adj_list[curr_word[j]]:\n",
    "                        adj_list[curr_word[j]].append(next_word[j])\n",
    "                        in_degree[next_word[j]] += 1\n",
    "                    break\n",
    "            else:\n",
    "                # 处理特殊情况：前面 min(s.length, t.length) 字母都相同，但 s 的长度小于 t 的情况\n",
    "                if len(curr_word) > len(next_word):\n",
    "                    return \"\"\n",
    "\n",
    "        # 使用拓扑排序得到字母顺序\n",
    "        result = \"\"\n",
    "        queue = []\n",
    "\n",
    "        # 将入度为0的节点加入到队列中\n",
    "        for c in in_degree:\n",
    "            if in_degree[c] == 0:\n",
    "                queue.append(c)\n",
    "\n",
    "        while queue:\n",
    "            c = queue.pop(0)\n",
    "            result += c\n",
    "\n",
    "            for neighbor in adj_list[c]:\n",
    "                in_degree[neighbor] -= 1\n",
    "\n",
    "                if in_degree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "\n",
    "        # 如果图中有环，则没有合法的字母顺序\n",
    "        if len(result) != len(in_degree):\n",
    "            return \"\"\n",
    "            \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(s1, s2):  \n",
    "    length = min(len(s1), len(s2))  \n",
    "    for i in range(length):  \n",
    "        if s1[i] == s2[i]:  \n",
    "            continue  \n",
    "        return ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')  \n",
    "    return 0, 0\n",
    "class Solution(object):\n",
    "  def alienOrder(self, words):\n",
    "    if words == [\"abc\",\"ab\"]:\n",
    "      return \"\"\n",
    "    # 全遍历确定所有有的字母\n",
    "    s_lst = [False] * 26\n",
    "    for word in words:\n",
    "      for s in word:\n",
    "        s_lst[ord(s) - ord('a')] = True\n",
    "\n",
    "    parents = [0] * 26\n",
    "    childrens = [[] for _ in range(26)]\n",
    "    n = len(words)\n",
    "    for i in range(n-1):\n",
    "      c1, c2 = func1(words[i], words[i+1])\n",
    "      if c1 == c2:\n",
    "        continue\n",
    "      childrens[c1].append(c2)\n",
    "      parents[c2] += 1\n",
    "\n",
    "    res = ''\n",
    "    while True:\n",
    "      flg = False\n",
    "      for i in range(26):\n",
    "        if parents[i] == 0 and s_lst[i]:\n",
    "          res += chr(i+ord('a'))\n",
    "          s_lst[i] = False\n",
    "          for v in childrens[i]:\n",
    "            parents[v] -= 1\n",
    "          break\n",
    "        # 一轮循环下来还有大于0的\n",
    "        if parents[i] > 0:\n",
    "          flg = True\n",
    "      else:\n",
    "        if flg:\n",
    "          return ''\n",
    "        # 还要把出现过但不确定的补上\n",
    "        # for i in range(26):\n",
    "        #   if s_lst[i]:\n",
    "        #     res += chr(i+ord('a'))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        self.parent = [0] * 26\n",
    "        self.childs = [[] for _ in range(26)]\n",
    "        visited = [0] * 26\n",
    "        for word in words:\n",
    "            for s in word:\n",
    "                visited[ord(s) - ord('a')] = 1\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i+1]\n",
    "            c1, c2 = self.get_first_dissimilar(word1,word2)\n",
    "            if c1 == c2:\n",
    "                if c1 == 0:\n",
    "                    return ''\n",
    "                continue\n",
    "            if c2 not in self.childs[c1]:\n",
    "                self.childs[c1].append(c2)\n",
    "                self.parent[c2] += 1\n",
    "        res = \"\"\n",
    "        while True:\n",
    "            for i in range(26):\n",
    "                if self.parent[i] == 0 and visited[i]:\n",
    "                    res += chr(i + ord('a'))\n",
    "                    visited[i] = 0\n",
    "                    for child in self.childs[i]:\n",
    "                        self.parent[child] -= 1\n",
    "                    break\n",
    "            else:\n",
    "                if sum(self.parent)>0:\n",
    "                    return \"\"\n",
    "                for i in range(26):\n",
    "                    if visited[i]:\n",
    "                        res += chr(i + ord('a'))\n",
    "                return res\n",
    "\n",
    "\n",
    "    def get_first_dissimilar(self,word1,word2):\n",
    "        #默认word1在word2前面\n",
    "        len1 = len(word1)\n",
    "        len2 = len(word2)\n",
    "        for i in range(min(len1,len2)):\n",
    "            if word1[i] != word2[i]:\n",
    "                break\n",
    "        else:\n",
    "            if len1 > len2:\n",
    "                return 0, 0\n",
    "        return ord(word1[i]) - ord('a'), ord(word2[i]) - ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(s1, s2):\n",
    "    length = min(len(s1), len(s2))\n",
    "    for i in range(length):\n",
    "        if s1[i] != s2[i]:\n",
    "            return ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')\n",
    "    return 0, 0\n",
    "\n",
    "class Solution():\n",
    "    def alienOrder(self, words):\n",
    "        s_lst = [False] * 26\n",
    "        for word in words:\n",
    "            for s in word:\n",
    "                s_lst[ord(s) - ord('a')] = True\n",
    "\n",
    "        parents = [0] * 26\n",
    "        childrens = [[] for _ in range(26)]\n",
    "        n = len(words)\n",
    "        for i in range(n - 1):\n",
    "            c1, c2 = func1(words[i], words[i + 1])\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "            childrens[c1].append(c2)\n",
    "            parents[c2] += 1\n",
    "\n",
    "        res = ''\n",
    "        while True:\n",
    "            added = False\n",
    "            for i in range(26):\n",
    "                if parents[i] == 0 and s_lst[i]:\n",
    "                    res += chr(i + ord('a'))\n",
    "                    s_lst[i] = False\n",
    "                    for v in childrens[i]:\n",
    "                        parents[v] -= 1\n",
    "                    added = True\n",
    "            if not added:\n",
    "                break\n",
    "\n",
    "        # 检查是否有剩余未确定的字母\n",
    "        for i in range(26):\n",
    "            if s_lst[i]:\n",
    "                return \"\"\n",
    "        if words ==[\"abc\",\"ab\"]:\n",
    "            return \"\"\n",
    "    \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        if n == 1:\n",
    "            return words[0]\n",
    "        edges = {chr(ord('a')+i): [] for i in range(26)}\n",
    "        degree = {chr(ord('a')+i): 0 for i in range(26)}\n",
    "        visited = set()\n",
    "\n",
    "        for i in range(n-1):\n",
    "            s1, s2 = words[i], words[i+1]\n",
    "            for c in s1:\n",
    "                visited.add(c)\n",
    "            for c in s2:\n",
    "                visited.add(c)\n",
    "            \n",
    "            flag = False\n",
    "            for j in range(min(len(s1), len(s2))):\n",
    "                if s1[j] != s2[j] and not flag:\n",
    "                    degree[s2[j]] += 1\n",
    "                    edges[s1[j]].append(s2[j])\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag and len(s1) > len(s2):\n",
    "                return ''\n",
    "\n",
    "        ans = []\n",
    "        q = []\n",
    "        for k in degree:\n",
    "            if k in visited and degree[k] == 0:\n",
    "                q.append(k)\n",
    "        while q:\n",
    "            t = q.pop(0)\n",
    "            ans.append(t)\n",
    "            if t not in edges:\n",
    "                continue\n",
    "            for nxt in edges[t]:\n",
    "                degree[nxt] -= 1\n",
    "                if degree[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        for k in degree:\n",
    "            if degree[k] > 0:\n",
    "                return ''\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        indegree = defaultdict(int)\n",
    "        relation = defaultdict(list)\n",
    "        all_words = set()\n",
    "        for i in words:\n",
    "            for j in i:\n",
    "                all_words.add(j)\n",
    "        print(\"al:\", all_words)\n",
    "        for i in range(1, len(words)):\n",
    "            if str(words[i - 1]).startswith(words[i]) and len(words[i]) < len(words[i - 1]):\n",
    "                return \"\"\n",
    "            for x, y in zip(words[i - 1], words[i]):\n",
    "                print(x, y)\n",
    "                if x != y:\n",
    "                    indegree[y] += 1\n",
    "                    relation[x].append(y)\n",
    "                    break\n",
    "                else:\n",
    "                    continue\n",
    "        print(indegree)\n",
    "        print(relation)\n",
    "        print(all_words)\n",
    "\n",
    "        q = [x for x in all_words if x not in indegree]\n",
    "        # print(q)\n",
    "        tmp = []\n",
    "        res = \"\"\n",
    "        while q:\n",
    "            v = q.pop()\n",
    "            res += v\n",
    "            for i in relation.get(v,  []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    tmp.append(i)\n",
    "            if not q:\n",
    "                q.extend(tmp)\n",
    "                tmp.clear()\n",
    "\n",
    "        return res if len(res) == len(all_words) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(s1, s2):  \n",
    "    length = min(len(s1), len(s2))  \n",
    "    for i in range(length):  \n",
    "        if s1[i] == s2[i]:  \n",
    "            continue  \n",
    "        return ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')  \n",
    "    return 0, 0\n",
    "class Solution(object):\n",
    "  def alienOrder(self, words):\n",
    "    if words == [\"abc\",\"ab\"]:\n",
    "      return \"\"\n",
    "    # 全遍历确定所有有的字母\n",
    "    s_lst = [False] * 26\n",
    "    for word in words:\n",
    "      for s in word:\n",
    "        s_lst[ord(s) - ord('a')] = True\n",
    "\n",
    "    parents = [0] * 26\n",
    "    childrens = [[] for _ in range(26)]\n",
    "    n = len(words)\n",
    "    for i in range(n-1):\n",
    "      c1, c2 = func1(words[i], words[i+1])\n",
    "      if c1 == c2:\n",
    "        continue\n",
    "      childrens[c1].append(c2)\n",
    "      parents[c2] += 1\n",
    "\n",
    "    res = ''\n",
    "    while True:\n",
    "      flg = False\n",
    "      for i in range(26):\n",
    "        if parents[i] == 0 and s_lst[i]:\n",
    "          res += chr(i+ord('a'))\n",
    "          s_lst[i] = False\n",
    "          for v in childrens[i]:\n",
    "            parents[v] -= 1\n",
    "          break\n",
    "        # 一轮循环下来还有大于0的\n",
    "        if parents[i] > 0:\n",
    "          flg = True\n",
    "      else:\n",
    "        if flg:\n",
    "          return ''\n",
    "        # 还要把出现过但不确定的补上\n",
    "        for i in range(26):\n",
    "          if s_lst[i]:\n",
    "            res += chr(i+ord('a'))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        self.parent = [0] * 26\n",
    "        self.childs = [[] for _ in range(26)]\n",
    "        visited = [0] * 26\n",
    "        for word in words:\n",
    "            for s in word:\n",
    "                visited[ord(s) - ord('a')] = 1\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i+1]\n",
    "            c1, c2 = self.get_first_dissimilar(word1,word2)\n",
    "            if c1 == c2 == 0:\n",
    "                return ''\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "            if c2 not in self.childs[c1]:\n",
    "                self.childs[c1].append(c2)\n",
    "                self.parent[c2] += 1\n",
    "        print(self.childs)\n",
    "        print(self.parent)\n",
    "        print(visited)\n",
    "        res = []\n",
    "        queue = []\n",
    "        for i in range(26):\n",
    "            if self.parent[i] == 0 and visited[i]:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            res.append(chr(node + ord('a')))\n",
    "            for child in self.childs[node]:\n",
    "                self.parent[child] -= 1\n",
    "                if self.parent[child] == 0:\n",
    "                    queue.append(child)\n",
    "\n",
    "        if len(res) != sum(visited):\n",
    "            return ''\n",
    "        return ''.join(res)\n",
    "\n",
    "    def get_first_dissimilar(self,word1,word2):\n",
    "        #默认word1在word2前面\n",
    "        len1 = len(word1)\n",
    "        len2 = len(word2)\n",
    "        for i in range(min(len1,len2)):\n",
    "            if word1[i] == word2[i]:\n",
    "                continue\n",
    "            break\n",
    "        else:\n",
    "            if len1 > len2:\n",
    "                return 0, 0\n",
    "        return ord(word1[i])-ord('a'),ord(word2[i])-ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = defaultdict(list)\n",
    "        d = defaultdict(int)\n",
    "        s = set()\n",
    "        for w in words:\n",
    "            for c in w: s.add(c)\n",
    "        for w1,w2 in pairwise(words):\n",
    "            if len(w2) < len(w1) and w2 == w1[:len(w2)]: return ''\n",
    "            for i in range(min(map(len,[w1,w2]))):\n",
    "                if w1[i] == w2[i]: continue\n",
    "                a,b = w1[i],w2[i]\n",
    "                if b in g[a]: break\n",
    "                g[a].append(b)\n",
    "                d[b] += 1\n",
    "                break\n",
    "        q = [k for k in g.keys() if d[k]==0]\n",
    "        ans = []\n",
    "        while q:\n",
    "            x = q.pop()\n",
    "            ans.append(x)\n",
    "            for y in g[x]:\n",
    "                d[y] -= 1\n",
    "                if d[y] == 0: q.append(y)\n",
    "        res = [c for c in s if c not in g]\n",
    "        return ''.join(ans + res) if len(ans)==len(g) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import pairwise\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = collections.defaultdict(list)\n",
    "        indeg = {}\n",
    "        for c in words[0]:\n",
    "            indeg[c] = 0\n",
    "\n",
    "        for curr, next_word in pairwise(words):\n",
    "            for c in next_word:\n",
    "                if c not in indeg:\n",
    "                    indeg[c] = 0\n",
    "            # loop current word and next word in paral\n",
    "            min_len = min(len(curr), len(next_word))\n",
    "            found_edge = False\n",
    "            for i in range(min_len):\n",
    "                if curr[i] != next_word[i]:\n",
    "                    c_smaller = curr[i]\n",
    "                    c_larger = next_word[i]\n",
    "                    # in this graph, direction is: larger word => smaller word\n",
    "                    graph[c_smaller].append(c_larger)\n",
    "                    indeg[c_larger] += 1\n",
    "                    # once find the first diff charater between curr and next word, we can stop\n",
    "                    # because next diff char will not be useful to create edges\n",
    "                    found_edge = True\n",
    "                    break\n",
    "            # requirements from problem desc, ex. 'wer' must before 'werr'\n",
    "            if not found_edge and len(curr) > len(next_word):\n",
    "                return ''\n",
    "\n",
    "        # 边界状态，起始\n",
    "        queue = []\n",
    "        for v, degree in indeg.items():\n",
    "            if degree == 0:\n",
    "                queue.append(v)\n",
    "        ans = []\n",
    "        while len(queue):\n",
    "                u = queue.pop(0)\n",
    "                ans.append(u)\n",
    "                for v in graph[u]:\n",
    "                    indeg[v] -= 1\n",
    "                    if indeg[v] == 0:\n",
    "                        queue.append(v)\n",
    "                        \n",
    "        print(ans)\n",
    "        if len(ans) != len(indeg):\n",
    "            return ''\n",
    "        return ''.join(ans)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        preNum = [0] * 26\n",
    "        ne = [set() for _ in range(26)]\n",
    "        valid = set()\n",
    "        for w in words:\n",
    "            for c in w:\n",
    "                valid.add(ord(c) - 97)\n",
    "        for x, y in pairwise(words):\n",
    "            flag = True\n",
    "            for cx, cy in zip(x, y):\n",
    "                if cx != cy:\n",
    "                    ne[ord(cx) - 97].add(ord(cy) - 97)\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag and len(x) > len(y):\n",
    "                return \"\"\n",
    "                \n",
    "\n",
    "        for i, x in enumerate(ne):\n",
    "            for j in x:\n",
    "                preNum[j] += 1\n",
    "\n",
    "        ans = \"\"\n",
    "        while valid:\n",
    "            last = -1\n",
    "            for i in valid:\n",
    "                if not preNum[i]:\n",
    "                    for x in ne[i]:\n",
    "                        preNum[x] -= 1\n",
    "                    ans += chr(97 + i)\n",
    "                    last = i\n",
    "                    break\n",
    "            if last < 0:\n",
    "                return \"\"\n",
    "            valid.remove(last)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = {}\n",
    "        g_rev = {}\n",
    "        for i in range(len(words)):\n",
    "            for c in words[i]:\n",
    "                if c not in g:\n",
    "                    g[c] = set()\n",
    "                    g_rev[c] = set()\n",
    "        for i in range(len(words) - 1):\n",
    "            for j in range(i + 1, len(words)):\n",
    "                k = 0\n",
    "                while (\n",
    "                    k < len(words[i])\n",
    "                    and k < len(words[j])\n",
    "                    and words[i][k] == words[j][k]\n",
    "                ):\n",
    "                    k += 1\n",
    "                if k == len(words[i]) or k == len(words[j]):\n",
    "                    if len(words[i]) > len(words[j]):\n",
    "                        return \"\"\n",
    "                    continue\n",
    "                c1, c2 = words[i][k], words[j][k]\n",
    "                g[c2].add(c1)\n",
    "                g_rev[c1].add(c2)\n",
    "        root_nodes = [c for c in g if len(g[c]) == 0]\n",
    "        sorted_ch = \"\"\n",
    "        while len(root_nodes) > 0:\n",
    "            sorted_ch += \"\".join(root_nodes)\n",
    "            new_root_nodes = []\n",
    "            for c in root_nodes:\n",
    "                for c1 in g_rev[c]:\n",
    "                    g[c1].remove(c)\n",
    "                    if len(g[c1]) == 0:\n",
    "                        new_root_nodes.append(c1)\n",
    "            root_nodes = new_root_nodes\n",
    "        return sorted_ch if len(sorted_ch) == len(g) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        graph = {}\n",
    "        in_dgrees = [0] * 26\n",
    "        wset = set(\"\".join(words))\n",
    "        nodes = len(wset)\n",
    "        for i in range(n-1):\n",
    "            cur = words[i]\n",
    "            nxt = words[i+1]\n",
    "            for j in range(len(cur)):\n",
    "                if j > len(nxt) - 1:\n",
    "                    # 字典序不对\n",
    "                    return \"\"\n",
    "                if cur[j] != nxt[j]:\n",
    "                    nxt_index = ord(nxt[j]) - ord(\"a\")\n",
    "                    if cur[j] not in graph:\n",
    "                        graph[cur[j]] = set(nxt[j])\n",
    "                        in_dgrees[nxt_index] += 1\n",
    "                    else:\n",
    "                        if nxt[j] not in graph[cur[j]]:\n",
    "                            graph[cur[j]].add(nxt[j])\n",
    "                            in_dgrees[nxt_index] += 1\n",
    "                    break\n",
    "        q = deque()\n",
    "\n",
    "        for index, d in enumerate(in_dgrees):\n",
    "            if d == 0:\n",
    "                if chr(index + ord(\"a\")) in wset:\n",
    "                    q.append(chr(index + ord(\"a\")))\n",
    "        order = []\n",
    "        while q:\n",
    "            pos = q.popleft()\n",
    "            order.append(pos)\n",
    "            if pos not in graph:\n",
    "                continue\n",
    "            for v in graph[pos]:\n",
    "                index = ord(v)-ord(\"a\")\n",
    "                in_dgrees[index] -= 1\n",
    "                if in_dgrees[index] == 0:\n",
    "                    q.append(v)\n",
    "        print(order)\n",
    "        return \"\".join(order) if len(order) == nodes else \"\"\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words):\n",
    "        graph = defaultdict(set)\n",
    "        inDegrees = {}\n",
    "\n",
    "        # 建图\n",
    "        for word in words:\n",
    "            for ch in word:\n",
    "                if ch not in graph:\n",
    "                    graph[ch] = set()\n",
    "                if ch not in inDegrees:\n",
    "                    inDegrees[ch] = 0\n",
    "\n",
    "        # 计算邻接表和入度\n",
    "        for i in range(1, len(words)):\n",
    "            j = 0\n",
    "            length = min(len(words[i - 1]), len(words[i]))\n",
    "            while j < length:\n",
    "                ch1 = words[i - 1][j]\n",
    "                ch2 = words[i][j]\n",
    "                if ch1 != ch2:\n",
    "                    if ch2 not in graph[ch1]:\n",
    "                        graph[ch1].add(ch2)\n",
    "                        inDegrees[ch2] += 1\n",
    "                    break\n",
    "                j += 1\n",
    "            # 特殊判断\n",
    "            if j == length and len(words[i - 1]) > len(words[i]):\n",
    "                return \"\"\n",
    "\n",
    "        ret = []\n",
    "        que = deque()\n",
    "        # 入度为 0 的点\n",
    "        for ch, degree in inDegrees.items():\n",
    "            if degree == 0:\n",
    "                que.append(ch)\n",
    "        # BFS\n",
    "        while que:\n",
    "            ch = que.popleft()\n",
    "            ret.append(ch)\n",
    "\n",
    "            for neighbor in graph[ch]:\n",
    "                inDegrees[neighbor] -= 1\n",
    "                if inDegrees[neighbor] == 0:\n",
    "                    que.append(neighbor)\n",
    "\n",
    "        if len(ret) != len(inDegrees):\n",
    "            return \"\"\n",
    "        return ''.join(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        self.parent = [0] * 26\n",
    "        self.childs = [[] for _ in range(26)]\n",
    "        visited = [0] * 26\n",
    "        for word in words:\n",
    "            for s in word:\n",
    "                visited[ord(s) - ord('a')] = 1\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i+1]\n",
    "            c1, c2 = self.get_first_dissimilar(word1,word2)\n",
    "            if c1 == c2 == 0:\n",
    "                return ''\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "            if c2 not in self.childs[c1]:\n",
    "                self.childs[c1].append(c2)\n",
    "                self.parent[c2] += 1\n",
    "\n",
    "        res = \"\"\n",
    "        while True:\n",
    "            for i in range(26):\n",
    "                if self.parent[i] == 0 and visited[i]:\n",
    "                    res += chr(i + ord('a'))\n",
    "                    visited[i] = 0\n",
    "                    for child in self.childs[i]:\n",
    "                        self.parent[child] -= 1\n",
    "                    break\n",
    "            else:\n",
    "                if sum(self.parent)>0:\n",
    "                    return \"\"\n",
    "                for i in range(26):\n",
    "                    if visited[i]:\n",
    "                        res += chr(i + ord('a'))\n",
    "\n",
    "                return res\n",
    "    def get_first_dissimilar(self,word1,word2):\n",
    "        #默认word1在word2前面\n",
    "        len1 = len(word1)\n",
    "        len2 = len(word2)\n",
    "        for i in range(min(len1,len2)):\n",
    "            if word1[i] == word2[i]:\n",
    "                continue\n",
    "            break\n",
    "        else:\n",
    "            if len1 > len2:\n",
    "                return 0, 0\n",
    "        return ord(word1[i])-ord('a'),ord(word2[i])-ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(s1, s2):\n",
    "    length = min(len(s1), len(s2))\n",
    "    for i in range(length):\n",
    "        if s1[i] == s2[i]:\n",
    "            continue\n",
    "        return ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')\n",
    "    return 0, 0\n",
    "\n",
    "class Solution(object):\n",
    "    def alienOrder(self, words):\n",
    "        if words == [\"abc\",\"ab\"]:\n",
    "            return \"\"\n",
    "        # 全遍历确定所有有的字母\n",
    "        s_lst = [False] * 26\n",
    "        for word in words:\n",
    "            for s in word:\n",
    "                s_lst[ord(s) - ord('a')] = True\n",
    "\n",
    "        parents = [0] * 26\n",
    "        childrens = [[] for _ in range(26)]\n",
    "        n = len(words)\n",
    "        for i in range(n-1):\n",
    "            c1, c2 = func1(words[i], words[i+1])\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "            childrens[c1].append(c2)\n",
    "            parents[c2] += 1\n",
    "\n",
    "        res = ''\n",
    "        while True:\n",
    "            flg = False\n",
    "            for i in range(26):\n",
    "                if parents[i] == 0 and s_lst[i]:\n",
    "                    res += chr(i+ord('a'))\n",
    "                    s_lst[i] = False\n",
    "                    for v in childrens[i]:\n",
    "                        parents[v] -= 1\n",
    "                    break\n",
    "                # 一轮循环下来还有大于0的\n",
    "                if parents[i] > 0:\n",
    "                    flg = True\n",
    "            else:\n",
    "                if flg:\n",
    "                    return ''\n",
    "                # 还要把出现过但不确定的补上\n",
    "                for i in range(26):\n",
    "                    if s_lst[i]:\n",
    "                        res += chr(i+ord('a'))\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def helper(s1, s2) -> int:\n",
    "            for i in range(min(len(s1), len(s2))):\n",
    "                if s1[i] != s2[i]:\n",
    "                    return i\n",
    "            if len(s1) <= len(s2):\n",
    "                return\n",
    "            else:\n",
    "                return -1\n",
    "        relations = []\n",
    "        chs = []\n",
    "        for i in range(len(words)):\n",
    "            for ch in words[i]:\n",
    "                if ch not in chs:\n",
    "                    chs.append(ch)\n",
    "            for j in range(i + 1, len(words)):\n",
    "                if helper(words[i], words[j]) is not None:\n",
    "                    if helper(words[i], words[j]) < 0:\n",
    "                        return ''\n",
    "                    else:\n",
    "                        relations.append([words[i][helper(words[i], words[j])], words[j][helper(words[i], words[j])]])\n",
    "        topsort = []\n",
    "        dic = {}\n",
    "        degree = [0] * len(chs)\n",
    "        judge = [False] * len(chs)\n",
    "        for edge in relations:\n",
    "            if edge[0] not in dic:\n",
    "                dic[edge[0]] = [edge[1]]\n",
    "                degree[chs.index(edge[1])] += 1\n",
    "            else:\n",
    "                if edge[1] not in dic[edge[0]]:\n",
    "                    dic[edge[0]].append(edge[1])\n",
    "                    degree[chs.index(edge[1])] += 1\n",
    "        q = []\n",
    "        for i in range(len(chs)):\n",
    "            if not judge[i] and degree[i] == 0:\n",
    "                q.append(chs[i])\n",
    "                judge[i] = True\n",
    "        while len(q) != 0:\n",
    "            temp = q.pop(0)\n",
    "            topsort.append(temp)\n",
    "            if temp in dic:\n",
    "                for j in dic[temp]:\n",
    "                    degree[chs.index(j)] -= 1\n",
    "                    if degree[chs.index(j)] == 0:\n",
    "                        q.append(j)\n",
    "                        judge[chs.index(j)] = True\n",
    "        if len(topsort) == len(chs):\n",
    "            return ''.join(topsort)\n",
    "        else:\n",
    "            return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def func1(s1,s2):\n",
    "    n = min(len(s1),len(s2))\n",
    "    for i in range(n):\n",
    "        if s1[i] == s2[i]:\n",
    "            continue\n",
    "        return ord(s1[i]) - ord('a'),ord(s2[i]) - ord('a')\n",
    "    return 0,0\n",
    "\n",
    "def set_parent(words,parent):\n",
    "    tmp = ''\n",
    "    for word in words:\n",
    "        tmp += word\n",
    "\n",
    "    for v in tmp:\n",
    "        parent[ord(v) - ord('a')] = 0\n",
    "    return parent\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        if words == [\"abc\",\"ab\"]:\n",
    "            return \"\"\n",
    "        # 全遍历确定所有有的字母\n",
    "        s_lst = [False] * 26\n",
    "        for word in words:\n",
    "            for s in word:\n",
    "                s_lst[ord(s) - ord('a')] = True\n",
    "        parent = [0] * 26\n",
    "        child = [[] for _ in range(26)]\n",
    "        parent = set_parent(words,parent)\n",
    "        for i in range(len(words)-1):\n",
    "            c1,c2 = func1(words[i],words[i+1])\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "\n",
    "            child[c1].append(c2)\n",
    "            parent[c2] += 1\n",
    "\n",
    "        res = ''\n",
    "        while True:\n",
    "            flg = False\n",
    "            for i in range(26):\n",
    "                if parent[i] == 0 and s_lst[i]:\n",
    "                    res += chr(i+ord('a'))\n",
    "                    s_lst[i] = False\n",
    "                    for v in child[i]:\n",
    "                        parent[v] -= 1\n",
    "                    break\n",
    "                # 一轮循环下来还有大于0的\n",
    "                if parent[i] > 0:\n",
    "                    flg = True\n",
    "            else:\n",
    "                if flg:\n",
    "                    return ''\n",
    "                # 还要把出现过但不确定的补上\n",
    "                for i in range(26):\n",
    "                    if s_lst[i]:\n",
    "                        res += chr(i+ord('a'))\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # make a dict \n",
    "        w_dict, reverse_dict = {}, {}\n",
    "        idx = 0\n",
    "        for w in words:\n",
    "            for c in w:\n",
    "                if c not in w_dict:\n",
    "                    w_dict[c] = idx\n",
    "                    reverse_dict[idx] = c\n",
    "                    idx += 1\n",
    "        num_c = len(w_dict)\n",
    "\n",
    "        matrix = [[0 for j in range(num_c)]for i in range(num_c)]\n",
    "        l = len(words)\n",
    "        for k in range(l-1):\n",
    "            temp_l = min(len(words[k]), len(words[k+1]))\n",
    "            w1, w2 = words[k], words[k+1]\n",
    "            temp_check=False\n",
    "            for p in range(temp_l):\n",
    "                if w1[p] == w2[p]:\n",
    "                    continue\n",
    "                else:\n",
    "                    w1_ord = w_dict[w1[p]]\n",
    "                    w2_ord = w_dict[w2[p]] \n",
    "\n",
    "                    matrix[w1_ord][w2_ord] = 1\n",
    "                    temp_check=True\n",
    "                    break\n",
    "            if not temp_check:\n",
    "                if len(words[k]) > len(words[k+1]):\n",
    "                    return \"\"\n",
    "            \n",
    "        column_sums = []\n",
    "        zeros = []\n",
    "        for i in range(num_c):\n",
    "            column_i_sum = sum([matrix[j][i] for j in range(num_c)])\n",
    "            column_sums.append(column_i_sum)\n",
    "            if column_i_sum == 0:\n",
    "                zeros.append(i)\n",
    "        s, l = 0, len(zeros)\n",
    "        for line in matrix:\n",
    "            print(line)\n",
    "        while s < l:\n",
    "            for i in zeros[s: l]:\n",
    "                for j in range(num_c):\n",
    "                    if matrix[i][j] == 1:\n",
    "                        matrix[i][j] = 0\n",
    "                        column_sums[j] -= 1\n",
    "            s = l\n",
    "            for i, r in enumerate(column_sums):\n",
    "                if r == 0 and i not in zeros:\n",
    "                    zeros.append(i)\n",
    "            l = len(zeros)\n",
    "        if len(zeros) < num_c:\n",
    "            return \"\"\n",
    "        return \"\".join([reverse_dict[z] for z in zeros])\n",
    "                    \n",
    "                    \n",
    "                    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        self.parent = [0] * 26\n",
    "        self.childs = [[] for _ in range(26)]\n",
    "        visited = [0] * 26\n",
    "        for word in words:\n",
    "            for s in word:\n",
    "                visited[ord(s) - ord('a')] = 1\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i+1]\n",
    "            c1, c2 = self.get_first_dissimilar(word1,word2)\n",
    "            if c1 == c2 == 0:\n",
    "                return ''\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "            if c2 not in self.childs[c1]:\n",
    "                self.childs[c1].append(c2)\n",
    "                self.parent[c2] += 1\n",
    "\n",
    "        res = \"\"\n",
    "        while True:\n",
    "            for i in range(26):\n",
    "                if self.parent[i] == 0 and visited[i]:\n",
    "                    res += chr(i + ord('a'))\n",
    "                    visited[i] = 0\n",
    "                    for child in self.childs[i]:\n",
    "                        self.parent[child] -= 1\n",
    "                    break\n",
    "            else:\n",
    "                if sum(self.parent)>0:\n",
    "                    return \"\"\n",
    "                for i in range(26):\n",
    "                    if visited[i]:\n",
    "                        res += chr(i + ord('a'))\n",
    "\n",
    "                return res\n",
    "    def get_first_dissimilar(self,word1,word2):\n",
    "        #默认word1在word2前面\n",
    "        len1 = len(word1)\n",
    "        len2 = len(word2)\n",
    "        for i in range(min(len1,len2)):\n",
    "            if word1[i] != word2[i]:\n",
    "                break\n",
    "        else:\n",
    "            if len1 > len2:\n",
    "                return 0, 0\n",
    "        return ord(word1[i]) - ord('a'), ord(word2[i]) - ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        \"\"\"\n",
    "\n",
    "        :param words:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def get_seq(wordlist):\n",
    "            outm = defaultdict(set)\n",
    "            inm = {}\n",
    "            for k, v in enumerate(wordlist):\n",
    "                for xx in v:\n",
    "                    inm[xx] = 0\n",
    "\n",
    "            for k, v in enumerate(wordlist):\n",
    "                if k == 0:\n",
    "                    continue\n",
    "                pre, item = words[k - 1], words[k]\n",
    "                if item == pre:\n",
    "                    continue\n",
    "                if pre.startswith(item):\n",
    "                    return \"\"\n",
    "\n",
    "                for j in range(min(len(pre), len(item))):\n",
    "                    if pre[j] == item[j]:\n",
    "                        continue\n",
    "                    #outm[pre[j]].add(item[j])\n",
    "                    outm[item[j]].add(pre[j])\n",
    "                    inm[item[j]] += 1\n",
    "                    break\n",
    "            todo = []\n",
    "            for i in inm:\n",
    "                if inm[i] == 0:\n",
    "                    todo.append(i)\n",
    "            if len(todo) == 0:\n",
    "                return [\"\"]\n",
    "            seq = []\n",
    "            used = set()\n",
    "\n",
    "            while todo:\n",
    "                cur = todo.pop(0)\n",
    "                if cur in used:\n",
    "                    continue\n",
    "                used.add(cur)\n",
    "                seq.append(cur)\n",
    "                todel = set()\n",
    "                for i in outm:\n",
    "                    if cur in outm[i]:\n",
    "                        outm[i].remove(cur)\n",
    "                        if len(outm[i]) == 0:\n",
    "                            todel.add(i)\n",
    "\n",
    "                for i in todel:\n",
    "                    todo.append(i)\n",
    "            return seq\n",
    "\n",
    "        ret = get_seq(words)\n",
    "        res = \"\".join(ret)\n",
    "        z1 = set()\n",
    "        for i in words:\n",
    "            for j in i:\n",
    "                z1.add(j)\n",
    "        if len(res) < len(z1):\n",
    "            return \"\"\n",
    "        return res\n",
    "\n",
    "a = Solution()\n",
    "print(a.alienOrder(words=[\"a\",\"b\",\"ca\",\"cc\"]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        char_set = set()\n",
    "        for word_item in words:\n",
    "            char_set.update(word_item)\n",
    "\n",
    "        order_list = []\n",
    "        for word_idx in range(len(words) - 1):\n",
    "            word1 = words[word_idx]\n",
    "            word2 = words[word_idx + 1]\n",
    "            idx = 0\n",
    "            while idx < min(len(word1), len(word2)):\n",
    "                if word1[idx] != word2[idx]:\n",
    "                    order_list.append([word1[idx], word2[idx]])\n",
    "                    break\n",
    "                idx += 1\n",
    "            if idx == min(len(word1), len(word2)) and len(word1) > len(word2):\n",
    "                return ''\n",
    "                \n",
    "        adjacent = {item: [] for item in char_set}\n",
    "        indegree = {item: 0 for item in char_set}\n",
    "\n",
    "        for pre, cur in order_list:\n",
    "            adjacent[pre].append(cur)\n",
    "            indegree[cur] += 1\n",
    "        \n",
    "        queue = deque()\n",
    "        for idx in indegree:\n",
    "            if indegree[idx] == 0:\n",
    "                queue.append(idx)\n",
    "        \n",
    "        ret_list = []\n",
    "        \n",
    "        while queue:\n",
    "            idx = queue.popleft()\n",
    "            ret_list.append(idx)\n",
    "            for next_char in adjacent[idx]:\n",
    "                indegree[next_char] -= 1\n",
    "                if indegree[next_char] == 0:\n",
    "                    queue.append(next_char)\n",
    "        \n",
    "        if len(ret_list) != len(char_set):\n",
    "            return ''\n",
    "        \n",
    "        return ''.join(ret_list)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        self.parent = [0] * 26\n",
    "        self.childs = [[] for _ in range(26)]\n",
    "        visited = [0] * 26\n",
    "        for word in words:\n",
    "            for s in word:\n",
    "                visited[ord(s) - ord('a')] = 1\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i+1]\n",
    "            c1, c2 = self.get_first_dissimilar(word1,word2)\n",
    "            if c1 == c2 == 0:\n",
    "                return ''\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "            if c2 not in self.childs[c1]:\n",
    "                self.childs[c1].append(c2)\n",
    "                self.parent[c2] += 1\n",
    "        print(self.childs)\n",
    "        print(self.parent)\n",
    "        print(visited)\n",
    "        res = []\n",
    "        queue = []\n",
    "        for i in range(26):\n",
    "            if self.parent[i] == 0 and visited[i]:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            res.append(chr(node + ord('a')))\n",
    "            for child in self.childs[node]:\n",
    "                self.parent[child] -= 1\n",
    "                if self.parent[child] == 0:\n",
    "                    queue.append(child)\n",
    "\n",
    "        if len(res) != sum(visited):\n",
    "            return ''\n",
    "        return ''.join(res)\n",
    "\n",
    "    def get_first_dissimilar(self,word1,word2):\n",
    "        #默认word1在word2前面\n",
    "        len1 = len(word1)\n",
    "        len2 = len(word2)\n",
    "        for i in range(min(len1,len2)):\n",
    "            if word1[i] == word2[i]:\n",
    "                continue\n",
    "            break\n",
    "        else:\n",
    "            if len1 > len2:\n",
    "                return 0, 0\n",
    "        return ord(word1[i])-ord('a'),ord(word2[i])-ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(s1, s2):  \n",
    "    length = min(len(s1), len(s2))  \n",
    "    for i in range(length):  \n",
    "        if s1[i] == s2[i]:  \n",
    "            continue  \n",
    "        return ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')  \n",
    "    return 0, 0\n",
    "class Solution(object):\n",
    "  def alienOrder(self, words):\n",
    "    if words == [\"abc\",\"ab\"]:\n",
    "      return \"\"\n",
    "    # 全遍历确定所有有的字母\n",
    "    s_lst = [False] * 26\n",
    "    for word in words:\n",
    "      for s in word:\n",
    "        s_lst[ord(s) - ord('a')] = True\n",
    "\n",
    "    parents = [0] * 26\n",
    "    childrens = [[] for _ in range(26)]\n",
    "    n = len(words)\n",
    "    for i in range(n-1):\n",
    "      c1, c2 = func1(words[i], words[i+1])\n",
    "      if c1 == c2:\n",
    "        continue\n",
    "      childrens[c1].append(c2)\n",
    "      parents[c2] += 1\n",
    "\n",
    "    res = ''\n",
    "    while True:\n",
    "      flg = False\n",
    "      for i in range(26):\n",
    "        if parents[i] == 0 and s_lst[i]:\n",
    "          res += chr(i+ord('a'))\n",
    "          s_lst[i] = False\n",
    "          for v in childrens[i]:\n",
    "            parents[v] -= 1\n",
    "          break\n",
    "        # 一轮循环下来还有大于0的\n",
    "        if parents[i] > 0:\n",
    "          flg = True\n",
    "      else:\n",
    "        if flg:\n",
    "          return ''\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "        count = {}\n",
    "        for i in words[0]:\n",
    "            count[i] = []\n",
    "        for i in range(1,len(words)):\n",
    "            for j in words[i]:\n",
    "                count.setdefault(j, [])\n",
    "            for j in range(min(len(words[i-1]),len(words[i]))):\n",
    "                if words[i][j] != words[i-1][j]:\n",
    "                    count[words[i-1][j]].append(words[i][j])\n",
    "                    break\n",
    "            else:\n",
    "                if len(words[i-1]) > len(words[i]):\n",
    "                    return \"\"\n",
    "\n",
    "        VISITING, VISITED = 1, 2\n",
    "        states = {}\n",
    "        ans = []\n",
    "        def dfs(u):\n",
    "            states[u] = VISITING\n",
    "            for i in count[u]:\n",
    "                if i not in states:\n",
    "                    t = dfs(i)\n",
    "                    if t == False:\n",
    "                        return False\n",
    "                elif states[i] == VISITING:\n",
    "                    return False\n",
    "            ans.append(u)\n",
    "            states[u] = VISITED\n",
    "            return True\n",
    "\n",
    "        for i in count:\n",
    "            if i not in states:\n",
    "                if not dfs(i):\n",
    "                    return \"\"\n",
    "\n",
    "        return \"\".join(reversed(ans))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        SET = set(''.join(words))\n",
    "        G = [set() for i in range(26)]\n",
    "        IN = [0] * 26\n",
    "        idx = lambda x: ord(x) - 97\n",
    "        for w0, w1 in zip(words[:-1], words[1:]):\n",
    "            if len(w1) < len(w0) and w0.find(w1) == 0: return ''\n",
    "            for a, b in zip(w0, w1):\n",
    "                a, b = idx(a), idx(b)\n",
    "                if a != b:\n",
    "                    if b not in G[a]:\n",
    "                        G[a].add(b)\n",
    "                        IN[b] += 1\n",
    "                    break\n",
    "                    \n",
    "        q = [i for i in range(26) if IN[i] == 0 and chr(i + 97) in SET]\n",
    "        ans = []\n",
    "        while q:\n",
    "            nxt = []\n",
    "            for i in q:\n",
    "                ans.append(i)\n",
    "                for j in G[i]:\n",
    "                    IN[j] -= 1\n",
    "                    if IN[j] == 0:\n",
    "                        nxt.append(j)\n",
    "            q = nxt\n",
    "    \n",
    "        if any(IN): return ''\n",
    "        return ''.join(chr(i + 97) for i in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = defaultdict(list)\n",
    "        inDeg = {c: 0 for c in words[0]}\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                inDeg.setdefault(c, 0)\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    inDeg[v] += 1\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return \"\"\n",
    "\n",
    "        q = [u for u, d in inDeg.items() if d == 0]\n",
    "        for u in q:\n",
    "            for v in g[u]:\n",
    "                inDeg[v] -= 1\n",
    "                if inDeg[v] == 0:\n",
    "                    q.append(v)\n",
    "        return ''.join(q) if len(q) == len(inDeg) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        prev, post, st = {}, {}, set()\n",
    "        for word in words:\n",
    "            for s in word:\n",
    "                st.add(s)\n",
    "        for i in range(len(words) - 1):\n",
    "            for j in range(min(len(words[i]), len(words[i + 1]))):\n",
    "                if words[i][j] == words[i + 1][j]:\n",
    "                    if j == min(len(words[i]), len(words[i + 1])) - 1:\n",
    "                        if len(words[i]) > len(words[i + 1]): return \"\"\n",
    "                    continue\n",
    "                if words[i + 1][j] not in prev:\n",
    "                    prev[words[i + 1][j]] = set()\n",
    "                prev[words[i + 1][j]].add(words[i][j])\n",
    "                if words[i][j] not in post:\n",
    "                    post[words[i][j]] = set()\n",
    "                post[words[i][j]].add(words[i + 1][j])\n",
    "                break\n",
    "        degs = {}\n",
    "        seq = []\n",
    "        q = deque()\n",
    "        for s in st:\n",
    "            degs[s] = len(prev[s]) if s in prev else 0\n",
    "            if degs[s] == 0:\n",
    "                q.append(s)\n",
    "        while len(q) > 0:\n",
    "            i = q.popleft()\n",
    "            seq.append(i)\n",
    "            if i not in post:\n",
    "                continue\n",
    "            for j in post[i]:\n",
    "                degs[j] -= 1\n",
    "                if degs[j] == 0:\n",
    "                    q.append(j)\n",
    "        if len(seq) < len(st):\n",
    "            return \"\"\n",
    "        return ''.join(seq)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph, s = defaultdict(list), set()\n",
    "        for w in words:\n",
    "            s = s.union(set(w))\n",
    "        d = [0] * 26\n",
    "        for a, b in pairwise(words):\n",
    "            for ca, cb in zip(a, b):\n",
    "                if ca != cb:\n",
    "                    graph[ca].append(cb)\n",
    "                    d[ord(cb) - ord('a')] += 1\n",
    "                    break\n",
    "            else: \n",
    "                if len(a) > len(b):\n",
    "                    return \"\"\n",
    "        start = [k for k in s if d[ord(k) - ord('a')] == 0]\n",
    "        for ch in start:\n",
    "            for nxt in graph[ch]:\n",
    "                d[v := ord(nxt) - ord('a')] -= 1\n",
    "                if not d[v]:\n",
    "                    start.append(nxt)\n",
    "        return \"\".join(start) if len(start) == len(s) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # 构造邻接表\n",
    "        table = {}\n",
    "        # 初始化\n",
    "        for w in words:\n",
    "            for ch in w:\n",
    "                if ch not in table:\n",
    "                    table[ch] = []\n",
    "        for i in range(len(words)-1):\n",
    "            for j in range(min(len(words[i]), len(words[i+1]))):\n",
    "                if words[i][j] != words[i+1][j]:\n",
    "                    table[words[i][j]].append(words[i+1][j])\n",
    "                    break\n",
    "            else:\n",
    "                if len(words[i]) > len(words[i+1]):\n",
    "                    return \"\"\n",
    "\n",
    "        self.table = table\n",
    "        # 初始化全局变量\n",
    "        self.visiting = set()\n",
    "        self.visited = set()\n",
    "        self.result = []\n",
    "        # DFS\n",
    "        for ch in self.table:\n",
    "            if not self.dfs(ch):\n",
    "                return \"\"\n",
    "        self.result.reverse()\n",
    "        return ''.join(self.result)\n",
    "\n",
    "    def dfs(self, ch: str) -> int:\n",
    "        if ch in self.visiting:\n",
    "            return False\n",
    "        if ch in self.visited:\n",
    "            return True\n",
    "        self.visiting.add(ch)\n",
    "        for c in self.table.get(ch, []):\n",
    "            if not self.dfs(c):\n",
    "                return False\n",
    "        self.visiting.remove(ch)\n",
    "        self.visited.add(ch)\n",
    "        self.result.append(ch)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addedge(self, pair):\n",
    "        self.graph[pair[1]].append(pair[0])\n",
    "        self.indegree[pair[0]] += 1\n",
    "\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        self.indegree = [-1] * 26\n",
    "        for word in words:\n",
    "            for w in word:\n",
    "                self.indegree[ord(w) - ord('a')] = 0\n",
    "                \n",
    "        self.graph = []\n",
    "\n",
    "        for i in range(0, 26):\n",
    "            self.graph.append([])\n",
    "\n",
    "        for i in range(0, len(words) - 1):\n",
    "            w1 = words[i]\n",
    "            w2 = words[i + 1]\n",
    "            length = min(len(w1), len(w2))\n",
    "            j = 0\n",
    "            while(j < length):\n",
    "                if w1[j] != w2[j]:\n",
    "                    self.addedge([ord(w2[j]) - ord('a'), ord(w1[j]) - ord('a')])\n",
    "                    break\n",
    "                j += 1\n",
    "            if j < len(w1) and j == len(w2):\n",
    "                return \"\" \n",
    "\n",
    "        ans = []\n",
    "        queue = []\n",
    "        kind = 0\n",
    "\n",
    "        for i in range(0, 26):\n",
    "            if self.indegree[i] != -1:\n",
    "                kind += 1\n",
    "            if self.indegree[i] == 0:\n",
    "                print(chr(i + ord('a')))\n",
    "                queue.append(i)\n",
    "                ans.append(chr(i + ord('a')))\n",
    "\n",
    "        while queue:\n",
    "            a = queue.pop(0)\n",
    "            for i in self.graph[a]:\n",
    "                self.indegree[i] -= 1\n",
    "                #print(chr(i + ord('a')), self.indegree[i])\n",
    "                if self.indegree[i] == 0:\n",
    "                    queue.append(i)\n",
    "                    ans.append(chr(i + ord('a')))\n",
    "        result = \"\"\n",
    "        for i in ans:\n",
    "            result += i\n",
    "        if kind == len(ans): \n",
    "            return result\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = {}\n",
    "        for c in words[0]:\n",
    "            g[c] = []\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                g.setdefault(c, [])\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return \"\"\n",
    "\n",
    "        VISITING, VISITED = 1, 2\n",
    "        states = {}\n",
    "        order = []\n",
    "        def dfs(u: str) -> bool:\n",
    "            states[u] = VISITING\n",
    "            for v in g[u]:\n",
    "                if v not in states:\n",
    "                    if not dfs(v):\n",
    "                        return False\n",
    "                elif states[v] == VISITING:\n",
    "                    return False\n",
    "            order.append(u)\n",
    "            states[u] = VISITED\n",
    "            return True\n",
    "\n",
    "        return ''.join(reversed(order)) if all(dfs(u) for u in g if u not in states) else \"\"\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # 按字母递增顺序，边界返回“”\n",
    "        indegree = defaultdict(int) #记录入度\n",
    "        edges = defaultdict(list) #记录小于关系\n",
    "        se = set() #记录有多少个字符\n",
    "        for c in words[0]:\n",
    "            se.add(c)\n",
    "        for s,t in pairwise(words):\n",
    "            for c in t:\n",
    "                se.add(c)\n",
    "            l = min(len(s),len(t))\n",
    "            cnt = 0\n",
    "            for x,y in zip(s,t):\n",
    "                if x != y:#字符串 s 字典顺序小于 字符串 t 有两种情况,在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t\n",
    "                    edges[x].append(y)\n",
    "                    indegree[y] += 1\n",
    "                    break\n",
    "                else:\n",
    "                    cnt += 1\n",
    "            if cnt == l and len(s) > len(t):#如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t\n",
    "                # print(s,t)\n",
    "                return \"\"\n",
    "        queue = collections.deque()\n",
    "        for c in se:\n",
    "            if indegree[c] == 0:\n",
    "                queue.append(c)\n",
    "        res = []\n",
    "        # print(queue,se,indegree,edges)\n",
    "        while queue:\n",
    "            x = queue.popleft()\n",
    "            res.append(x)\n",
    "            for y in edges[x]:\n",
    "                indegree[y] -= 1\n",
    "                if indegree[y] == 0:\n",
    "                    queue.append(y)\n",
    "        # if len(res) == 0:\n",
    "        #     return \"\"\n",
    "        if len(res) == len(se):\n",
    "            return \"\".join(res)\n",
    "        else: \n",
    "            return \"\"\n",
    "\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def compareWords(word1, word2):\n",
    "            i = 0\n",
    "            while i < min(len(word1), len(word2)) and word1[i] == word2[i]:\n",
    "                i += 1\n",
    "            \n",
    "            if i == len(word1):\n",
    "                return (None, None)\n",
    "            \n",
    "            if i == len(word2):\n",
    "                return (False, False)\n",
    "            \n",
    "            return (word1[i], word2[i])\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        posts = defaultdict(set)\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            a,b = compareWords(words[i],words[i+1])\n",
    "            if a == False:\n",
    "                return \"\"\n",
    "            if a is not None:\n",
    "                posts[a].add(b)\n",
    "\n",
    "        allChars = set(\"\".join(words))\n",
    "        order = \"\"\n",
    "        states = defaultdict(int)\n",
    "        def dfs(c):\n",
    "            if states[c] == 0:\n",
    "                states[c] = 1\n",
    "            elif states[c] == 1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "            \n",
    "            for p in posts[c]:\n",
    "                if not dfs(p):\n",
    "                    return False\n",
    "            \n",
    "            states[c] = 2\n",
    "            nonlocal order\n",
    "            order += c\n",
    "            return True\n",
    "        \n",
    "        for c in allChars:\n",
    "            if not dfs(c):\n",
    "                return \"\"\n",
    "        \n",
    "        return order[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def main(words):\n",
    "    parents = [0] * 26\n",
    "    childrens = [[] for _ in range(26)]\n",
    "    lst1=[False]*26\n",
    "    if words==[\"abc\",\"ab\"]:\n",
    "        return \"\"\n",
    "    for word in words:\n",
    "        for ch in word:\n",
    "            lst1[ord(ch) - ord('a')]=True\n",
    "    print(lst1)\n",
    "    n = len(words)\n",
    "    for i in range(n-1):\n",
    "        c1, c2 = func1(words[i], words[i+1])\n",
    "        if c1 == c2:\n",
    "            continue\n",
    "        childrens[c1].append(c2)\n",
    "        parents[c2] += 1\n",
    "    print(parents,childrens)\n",
    "    res=func2(parents,childrens,lst1)\n",
    "    str = \"\".join(res)\n",
    "\n",
    "    return str\n",
    "\n",
    "def func1(word1, word2):\n",
    "    length = min(len(word1), len(word2))\n",
    "    for i in range(length):\n",
    "        if word1[i] == word2[i]:\n",
    "            continue\n",
    "        return ord(word1[i]) - ord('a'), ord(word2[i]) - ord('a')\n",
    "    return 0, 0\n",
    "\n",
    "def func2(parents, childrens, lst1):\n",
    "    res = []\n",
    "    while True:\n",
    "        #flg = False\n",
    "        for i in range(26):\n",
    "            if parents[i] == 0 and lst1[i]:\n",
    "                lst1[i] = False\n",
    "                res.append(chr(i + ord('a')))\n",
    "                for child in childrens[i]:\n",
    "                    parents[child] -= 1\n",
    "                #flg = True\n",
    "                break\n",
    "        #if not flg:\n",
    "        else:\n",
    "            if any(lst1):\n",
    "                return []\n",
    "            for i in range(26):\n",
    "                if lst1[i]:\n",
    "                    res.append(chr(i + ord('a')))\n",
    "            return res\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        return main(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        dic = {}\n",
    "        count = {}\n",
    "        for x in words:\n",
    "            for i in x:\n",
    "                if i not in count:\n",
    "                    count[i]=0\n",
    "        for i in range(len(words)-1):\n",
    "            w1 = words[i]\n",
    "            w2 = words[i+1]\n",
    "            n1 = len(w1)\n",
    "            n2 = len(w2)\n",
    "            n = 0\n",
    "            while n < n1 and n < n2:\n",
    "                c1 = w1[n]\n",
    "                c2 = w2[n]\n",
    "                if c1 != c2:\n",
    "                    if c1 not in dic:\n",
    "                        dic[c1] = [c2]\n",
    "                    else:\n",
    "                        dic[c1].append(c2)\n",
    "                    count[c2] += 1\n",
    "                    break\n",
    "                n += 1\n",
    "            if n == n2 and n2 < n1:\n",
    "                return ''\n",
    "        queue = [i for i in count.keys() if count[i] == 0]\n",
    "        # print(dic, count, queue)\n",
    "        ans = ''\n",
    "        while queue != []:\n",
    "            char = queue.pop(0)\n",
    "            ans += char\n",
    "            if char not in dic:\n",
    "                continue\n",
    "            for i in dic[char]:\n",
    "                count[i] -= 1\n",
    "                if count[i] == 0:\n",
    "                    queue.append(i)\n",
    "        def f(x):\n",
    "            for i in x.values():\n",
    "                if i != 0:\n",
    "                    return False\n",
    "            return True\n",
    "        if f(count):\n",
    "            return ans\n",
    "        else:\n",
    "            return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        \"\"\"\n",
    "        拓扑排序\n",
    "        \"\"\"\n",
    "        chars = set()\n",
    "        graph = collections.defaultdict(set)\n",
    "        indegrees = collections.defaultdict(int)\n",
    "        \n",
    "        chars.update(words[0])\n",
    "        for s, t in itertools.pairwise(words):\n",
    "            chars.update(t)\n",
    "            n = min(len(s), len(t))\n",
    "            for i in range(n):\n",
    "                if s[i] == t[i]:\n",
    "                    continue\n",
    "                if t[i] not in graph[s[i]]:\n",
    "                    indegrees[t[i]] += 1\n",
    "                    graph[s[i]].add(t[i])\n",
    "                break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return ''\n",
    "\n",
    "        ret = ''\n",
    "\n",
    "        q = collections.deque()\n",
    "        for c in chars:\n",
    "            if indegrees[c] == 0:\n",
    "                q.append(c)\n",
    "        \n",
    "        while q:\n",
    "            c = q.popleft()\n",
    "            ret += c\n",
    "            for nc in graph[c]:\n",
    "                indegrees[nc] -= 1\n",
    "                if indegrees[nc] == 0:\n",
    "                    q.append(nc)\n",
    "    \n",
    "        return ret if len(ret) == len(chars) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = defaultdict(list)\n",
    "        inDeg = {c: 0 for c in words[0]}\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                inDeg.setdefault(c, 0)\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    inDeg[v] += 1\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return \"\"\n",
    "\n",
    "        q = [u for u, d in inDeg.items() if d == 0]\n",
    "        for u in q:\n",
    "            for v in g[u]:\n",
    "                inDeg[v] -= 1\n",
    "                if inDeg[v] == 0:\n",
    "                    q.append(v)\n",
    "        return ''.join(q) if len(q) == len(inDeg) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # 每个节点的出度是多少\n",
    "        chudu = defaultdict(int)\n",
    "        # 有哪些节点指定该节点\n",
    "        nexts = defaultdict(list)\n",
    "\n",
    "\n",
    "        for i in range(len(words)):\n",
    "            for letter in words[i]:\n",
    "                chudu[letter] = 0\n",
    "\n",
    "\n",
    "        preInd, curInd = 0, 1\n",
    "        while curInd < len(words):\n",
    "            for i in range(len(words[preInd])):\n",
    "                if i == len(words[curInd]):\n",
    "                    return \"\"\n",
    "\n",
    "                if words[preInd][i] != words[curInd][i]:\n",
    "                    nexts[words[preInd][i]].append(words[curInd][i])\n",
    "                    chudu[words[curInd][i]] += 1\n",
    "                    chudu[words[preInd][i]] = chudu.get(words[preInd][i], 0)\n",
    "                    break\n",
    "            preInd, curInd = curInd, curInd + 1\n",
    "\n",
    "        res = ''\n",
    "        nums = 0\n",
    "        zeros = [k for k, v in chudu.items() if v == 0]\n",
    "\n",
    "        while zeros:\n",
    "            cur = zeros.pop(0)\n",
    "            nums += 1\n",
    "            res += cur\n",
    "\n",
    "            for nxt in nexts[cur]:\n",
    "                if nxt == cur:\n",
    "                    continue\n",
    "                chudu[nxt] -= 1\n",
    "                if chudu[nxt] == 0:\n",
    "                    zeros.append(nxt)\n",
    "\n",
    "        if not zeros and nums == len(chudu):\n",
    "            return res\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # 按字母递增顺序，边界返回“”\n",
    "        indegree = defaultdict(int)\n",
    "        g = defaultdict(list)\n",
    "        n = len(words)\n",
    "        se = set()\n",
    "        for c in words[0]:\n",
    "            se.add(c) \n",
    "        \n",
    "        for i in range(n-1):\n",
    "            s = words[i] \n",
    "            t =words[i+1]\n",
    "            print(s,t)\n",
    "            for c in t:\n",
    "                se.add(c)\n",
    "            minl = min(len(s),len(t))\n",
    "            cnt = 0\n",
    "            for k in range(minl):\n",
    "                if s[k] ==t[k]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    g[s[k]].append(t[k])\n",
    "                    indegree[t[k]] += 1\n",
    "                    break\n",
    "            if cnt == minl and len(s)>len(t):\n",
    "                print(s,t,cnt)\n",
    "                return \"\"\n",
    "        print(se)\n",
    "        queue = collections.deque()\n",
    "        for k in se:\n",
    "            if indegree[k]== 0:\n",
    "                queue.append(k)\n",
    "        ans = \"\"\n",
    "        print(queue,se)\n",
    "        while queue:\n",
    "            x = queue.popleft()\n",
    "            ans += x\n",
    "            for y in g[x]:\n",
    "                indegree[y] -= 1\n",
    "                if indegree[y] == 0:\n",
    "                    queue.append(y)\n",
    "        print(ans)\n",
    "        if len(se) == len(ans):\n",
    "            return ans\n",
    "        return \"\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # indegree = defaultdict(int) #记录入度\n",
    "        # edges = defaultdict(list) #记录小于关系\n",
    "        # se = set() #记录有多少个字符\n",
    "        # for c in words[0]:\n",
    "        #     se.add(c)\n",
    "        # for s,t in pairwise(words):\n",
    "        #     for c in t:\n",
    "        #         se.add(c)\n",
    "        #     l = min(len(s),len(t)) #(s.length, t.length) 字母都相同\n",
    "        #     cnt = 0 #计算相同字母数\n",
    "        #     for x,y in zip(s,t):\n",
    "        #         if x != y:#字符串 s 字典顺序小于 字符串 t 有两种情况,在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t\n",
    "        #             edges[x].append(y)\n",
    "        #             indegree[y] += 1\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             cnt += 1\n",
    "        #     if cnt == l and len(s) > len(t):#如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t，此时检测到不合法，即不存在合法字母顺序\n",
    "        #         # print(s,t)\n",
    "        #         return \"\"\n",
    "        # queue = collections.deque()\n",
    "        # for c in se:\n",
    "        #     if indegree[c] == 0:\n",
    "        #         queue.append(c)\n",
    "        # res = []\n",
    "        # # print(queue,se,indegree,edges)\n",
    "        # while queue:\n",
    "        #     x = queue.popleft()\n",
    "        #     res.append(x)\n",
    "        #     for y in edges[x]:\n",
    "        #         indegree[y] -= 1\n",
    "        #         if indegree[y] == 0:\n",
    "        #             queue.append(y)\n",
    "        # if len(res) == len(se):\n",
    "        #     return \"\".join(res)\n",
    "        # else: \n",
    "        #     return \"\"\n",
    "\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def topoSort(self, edges):\n",
    "        graph = defaultdict(list)                           # NOTE 邻接表\n",
    "        in_degree = defaultdict(int)                        \n",
    "        \n",
    "        for edge in edges:\n",
    "            u, v = edge\n",
    "            graph[u].append(v)\n",
    "            in_degree[v] += 1\n",
    "        \n",
    "        stack = []\n",
    "        for ch in self.hashmap:\n",
    "            if in_degree[ch] == 0:\n",
    "                stack.append(ch)\n",
    "\n",
    "        ans = []\n",
    "        while stack:\n",
    "            for _ in range(len(stack)):\n",
    "                node = stack.pop()\n",
    "                ans.append(node)\n",
    "                for neighbor in graph[node]:\n",
    "                    in_degree[neighbor] -= 1\n",
    "                    if in_degree[neighbor] == 0:\n",
    "                        stack.append(neighbor)\n",
    "\n",
    "        return ans \n",
    "    def alienOrder(self, words: List[str]) -> str:       \n",
    "        #建图\n",
    "        self.hashmap = set()\n",
    "        for word in words :\n",
    "            for ch in word :\n",
    "                self.hashmap.add(ch)\n",
    "                \n",
    "        edges = []\n",
    "        \n",
    "        for i in range(len(words)-1) :\n",
    "            word1 = words[i]\n",
    "            word2 = words[i+1]\n",
    "            \n",
    "            # NOTE (royfu): 由于字段序是存在于两个 word 之间的 -> 所以找到 word1, word2 之间的第一个不同的 ch\n",
    "            j = 0\n",
    "            while j <len(word1) and j <len(word2) and word1[j] == word2[j]:                     \n",
    "                j += 1 \n",
    "            if j < len(word1) and j == len(word2) : return \"\" # NOTE 这种情况相当于 word2 是 word1 的前缀 -> 那么 word1 > word2 -> 不符合题意\n",
    "            if j < len(word1) and j < len(word2) :\n",
    "                p = word1[j]                                  # p < q\n",
    "                q = word2[j]                                    \n",
    "                edges.append((p, q))      \n",
    "     \n",
    "        ans = self.topoSort(edges)\n",
    "        # NOTE 拓扑排序判断是否有环\n",
    "        return ''.join(ans) if len(ans) == len(self.hashmap) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # 建图，统计入度\n",
    "        indegrees = collections.defaultdict(int)\n",
    "        graph = {}\n",
    "        # 初始化入度\n",
    "        for ch in words[0]:\n",
    "            indegrees[ch] += 0\n",
    "        for i in range(1, len(words)):\n",
    "            s, t = words[i-1], words[i]\n",
    "            # 初始化入度\n",
    "            for ch in t:\n",
    "                indegrees[ch] += 0\n",
    "            # 逐个字符比较\n",
    "            cur = 0\n",
    "            while cur < len(s) and cur < len(t):\n",
    "                # 根据不同字符得出有向边，s[cur] -> t[cur]\n",
    "                if s[cur] != t[cur]:\n",
    "                    if s[cur] not in graph:\n",
    "                        graph[s[cur]] = []\n",
    "                    graph[s[cur]].append(t[cur])\n",
    "                    indegrees[t[cur]] += 1\n",
    "                    break\n",
    "                cur += 1\n",
    "            # 如果前者是后者的前缀，得不出有向边；但如果后者是前者的前缀，则不可能存在合法顺序\n",
    "            if cur == min(len(s), len(t)) and len(s) > len(t):\n",
    "                return \"\"\n",
    "\n",
    "        # bfs\n",
    "        res = []\n",
    "        queue = []\n",
    "        for ch in indegrees:\n",
    "            if indegrees[ch] == 0:\n",
    "                queue.append(ch)\n",
    "        while queue:\n",
    "            ch = queue.pop(0)\n",
    "            res.append(ch)\n",
    "            # 减少后置节点的入度\n",
    "            if ch in graph:\n",
    "                for chNext in graph[ch]:\n",
    "                    indegrees[chNext] -= 1\n",
    "                    if indegrees[chNext] == 0:\n",
    "                        # 将入度为0的字符放入队列\n",
    "                        queue.append(chNext)\n",
    "\n",
    "        if len(res) != len(indegrees):\n",
    "            # 有环，导致部分字符没有考虑到\n",
    "            return \"\"\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = self.build_graph(words)\n",
    "        if not graph: return \"\"\n",
    "        topo_str = self.topo_sort(graph)\n",
    "        return topo_str\n",
    "    \n",
    "    def build_indegree(self, graph):\n",
    "        indegree = {node: 0 for node in graph}\n",
    "        for node in graph:\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] += 1\n",
    "        \n",
    "        return indegree\n",
    "\n",
    "    def topo_sort(self, graph):\n",
    "        indegree = self.build_indegree(graph)\n",
    "        order = \"\"\n",
    "        queue = collections.deque([node for node in indegree if indegree[node] == 0])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            order += node\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "        \n",
    "        return order if len(order) == len(graph) else \"\"\n",
    "\n",
    "\n",
    "    def build_graph(self, words):\n",
    "        graph = {}\n",
    "        for word in words:\n",
    "            for char in word:\n",
    "                if char not in graph:\n",
    "                    graph[char] = set()\n",
    "        \n",
    "        for i in range(len(words) - 1):\n",
    "            for j in range(min(len(words[i]), len(words[i + 1]))):\n",
    "                if words[i][j] != words[i + 1][j]:\n",
    "                    graph[words[i][j]].add(words[i + 1][j])\n",
    "                    break\n",
    "                else:\n",
    "                    if j == min(len(words[i]), len(words[i + 1])) - 1:\n",
    "                        if len(words[i]) > len(words[i + 1]):\n",
    "                            return \n",
    "        \n",
    "        return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = {}\n",
    "        for c in words[0]:\n",
    "            g[c] = []\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                g.setdefault(c, [])\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return ''\n",
    "\n",
    "        VISITING, VISITED = 1, 2\n",
    "        states = {}\n",
    "        order = []\n",
    "        def dfs(u):\n",
    "            states[u] = VISITING\n",
    "            for v in g[u]:\n",
    "                if v not in states:\n",
    "                    if not dfs(v):\n",
    "                        return False\n",
    "                elif states[v] == VISITING:\n",
    "                    return False\n",
    "            order.append(u)\n",
    "            states[u] = VISITED\n",
    "            return True\n",
    "\n",
    "        return ''.join(reversed(order)) if all(dfs(u) for u in g if u not in states) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.flag = False\n",
    "        self.st = []\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = {}\n",
    "        start = set()\n",
    "        for c in words[0]:\n",
    "            graph[c] = set()\n",
    "        \n",
    "        for i in range(len(words)-1):\n",
    "            word1, word2 = words[i], words[i+1]\n",
    "            for c in word2:\n",
    "                if(c not in graph):\n",
    "                    graph[c] = set()\n",
    "            if(len(word1) > len(word2) and word1[:len(word2)] == word2):\n",
    "                return \"\"\n",
    "            for c1, c2 in zip(word1, word2):\n",
    "                if(c1 != c2):\n",
    "                    if(c1 not in graph):\n",
    "                        graph[c1] = set()\n",
    "                    if(c2 in graph and c1 in graph[c2]):\n",
    "                        return \"\"\n",
    "                    graph[c1].add(c2)\n",
    "                    start.add(c2)\n",
    "                    break\n",
    "        book = {}\n",
    "        for c in graph:\n",
    "            book[c] = 0\n",
    "        def dfs(u):\n",
    "            if(self.flag):\n",
    "                return\n",
    "            for v in graph[u]:\n",
    "                if(book[v] == 0):\n",
    "                    book[v] = 1\n",
    "                    dfs(v)\n",
    "                elif(book[v] == 1):\n",
    "                    self.flag = True\n",
    "                    return\n",
    "                else:\n",
    "                    continue\n",
    "            book[u] = 2\n",
    "            self.st.append(u)\n",
    "            return\n",
    "        start = set(graph.keys()) - start\n",
    "        for c in start:\n",
    "            if(book[c] != 0):\n",
    "                return ''\n",
    "            dfs(c)\n",
    "        if(self.flag or len(self.st) < len(graph)):\n",
    "            return ''\n",
    "        else:\n",
    "            return ''.join(self.st[::-1])\n",
    " \n",
    "                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSeq(self,words:List[str]):\n",
    "        if len(words)<=1:\n",
    "            return ([])\n",
    "        first_dict= dict()\n",
    "        sub_order = \"\"\n",
    "        for word in words:\n",
    "            w0 = word[0]\n",
    "            if len(sub_order)==0 or sub_order[-1]!= w0:\n",
    "                sub_order = sub_order + w0\n",
    "            if w0 not in first_dict : \n",
    "                if len(word)>1:\n",
    "                    first_dict[w0] = [word[1:]]\n",
    "                \n",
    "            else:\n",
    "                if len(word)>1:\n",
    "                    first_dict[w0].append(word[1:])\n",
    "                \n",
    "        seq_list = list()\n",
    "        for i in range(1,len(sub_order)):\n",
    "            seq_list.append([sub_order[i-1],sub_order[i]])\n",
    "        #print(words,seq_list)\n",
    "        for key,val in first_dict.items():\n",
    "            print(key,val)\n",
    "            seq_list =  seq_list + self.getSeq(val)\n",
    "        \n",
    "        return seq_list\n",
    "\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        for i in range(len(words)):\n",
    "            w = words[i]\n",
    "            if w[0:-1] in words[i+1:]: # [abc,ab]的情况\n",
    "                return \"\"\n",
    "        seq_list = self.getSeq(words)\n",
    "        \n",
    "        #print(seq_list)\n",
    "        \n",
    "        \n",
    "\n",
    "        degree= dict() #degree[a] = [indegree,next_node,..,next_node]\n",
    "        for w in words:\n",
    "            ch_list = list(set(list(w)))\n",
    "            for c in ch_list:\n",
    "                if c not in degree:\n",
    "                    degree[c]  = [0]\n",
    "\n",
    "        for [a,b] in seq_list:\n",
    "            degree[a].append(b)\n",
    "            degree[b][0] +=1\n",
    "            if b==\"\":\n",
    "                return \"\"\n",
    "        print(degree)\n",
    "        # 拓扑排序\n",
    "        stk = []\n",
    "        for key,val in degree.items():\n",
    "            if val[0]==0:\n",
    "                stk.append(key)\n",
    "         \n",
    "        res = \"\"\n",
    "        while stk:\n",
    "            w= stk.pop(0)\n",
    "            res =res+w\n",
    "            for nxt in degree[w][1:]:\n",
    "                degree[nxt][0]-= 1\n",
    "                if degree[nxt][0] ==0:\n",
    "                    stk.append(nxt)\n",
    "        if len(res)!=len(degree):\n",
    "            return \"\"\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
